package com.java.comprehensive.arithmetic.leecode.tags.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: comprehensive-service
 * @description: 三数之和
 * @author: 窦绍飞
 * @create: 2021-12-08 10:55
 **/
public class LeetCode_15 {

	public static List<List<Integer>> threeSum(int[] nums) {

		List<List<Integer>> listList = new ArrayList<>();
		if (nums == null || nums.length < 3) return listList;
		// 先排序 从小到大
		Arrays.sort(nums);
		//拿出一个 位置的数字 用来相加每一个数字
		for (int i = 0; i < nums.length - 1; i++) {
			//如果小于大于零证明最小的已经大于0不可能  有结果了
			if (nums[i] > 0) return listList;
			//当前i 和之前的一样的话 在上一边 循环就会遍历出来
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			//确立 左右指针
			int l = i + 1, r = nums.length - 1;
			//左指针向右移 =右指针向左移和当前i 想加找到一个 等于0的三个数字
			while (l < r) {
				int temp = nums[l] + nums[r] + nums[i];
				if (temp == 0) {
					listList.add(Arrays.asList(nums[l], nums[r], nums[i]));
					//当前i 和之前的一样的话 在上一编 循环就会遍历出来
					while (l < r && nums[l] == nums[l + 1]) {
						l++;
					}
					//当前i 和之前的一样的话 在上一编  循环就会遍历出来
					l++;
					while (l < r && nums[r] == nums[r - 1]) {
						r--;
					}
					r--;
				} else {
					if (temp > 0) {
						r--;
					} else {
						l++;
					}
				}
			}
		}
		List<List<Integer>> result = new ArrayList<>();
		if (nums == null || nums.length < 3) return result;
		// 先排序 从小到大
		Arrays.sort(nums);
		for (int i = 0; i <= nums.length - 1; i++) {
			int l = i + 1;
			int r = nums.length - 1;
			if (nums[i] > 0) return result;
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			while (l < r) {
				if (nums[i] + nums[l] + nums[r] == 0) {
					result.add(Arrays.asList(nums[i], nums[l], nums[r]));
					while (l < r && nums[l] == nums[l + 1]) {
						l++;
					}
					l++;
					while (l < r && nums[r] == nums[r - 1]) {
						r--;
					}
					r--;
				} else {
					if (nums[i] + nums[l] + nums[r] > 0) {
						r--;
					} else {
						l++;
					}
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] nums = {-1, 0, 1, 2, -1, -4};
		List<List<Integer>> listList = threeSum(nums);
		System.out.println(Arrays.toString(new List[]{listList}));
	}
}
